Package edu.claflin.finder.algo

Class DepthFirstTraversalSearch

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.DepthFirstTraversalSearch

All Implemented Interfaces:

Processable<Graph,Graph>

public class DepthFirstTraversalSearch
extends Algorithm

Processes a Graph searching for bipartite subgraphs by performing a depth first search on each node.

Version:

3.4 February 4, 2016

Author:

Charles Allen Schultz II

Nested Class Summary

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields

Modifier and Type	Field	Description
private Comparator<Edge>	comparator

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
DepthFirstTraversalSearch(ArgumentsBundle bundle)	Public constructor for initializing the DepthFirstTraversalSearch with default conditions.

Method Summary

Modifier and Type	Method	Description
ArrayList<Graph>	process(Graph graph)	Processes data.
private Graph	searchNode(Graph graph, Graph subGraph, Node node, List<Node> visited)	Helper method to search for the SubGraphs in Depth First search.
private void	setComparator()
String	toString()

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getMinNodeCount, getPartiteNumber, getWeightName, removePropertyChangeListener, setGraphSortOrder, setMinNodeCount, setPartiteNumber, setProgress, setWeightName, zeropad

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

comparator

private Comparator<Edge> comparator

Constructor Details

DepthFirstTraversalSearch

public DepthFirstTraversalSearch(ArgumentsBundle bundle)

Public constructor for initializing the DepthFirstTraversalSearch with default conditions.

Parameters:

bundle - the ArgumentsBundle containing the instantiation arguments.

Method Details

toString

public String toString()

Overrides:

toString in class Object

process

public ArrayList<Graph> process(Graph graph)

Processes data.
Finds most Subgraphs by performing a depth first search on the node tree. It is unknown if it finds all or only most of the subgraphs due to the nature of the algorithm. It is expected, however, that it would miss certain node groupings.

Parameters:

graph - the Graph object to search through.

Returns:

the ArrayList of Graph objects holding all found subgraphs.

searchNode

private Graph searchNode(Graph graph,
 Graph subGraph,
 Node node,
 List<Node> visited)

Helper method to search for the SubGraphs in Depth First search. Loops recursively to search for subgraphs. Is called on each node in the tree.

Parameters:

graph - the Graph object to search through.

subGraph - the Graph object indicating the subgraph to store found nodes and edges in. (Used due to the recursive nature of the algorithm.)

node - the current node to search.

visited - the List containing the visited nodes.

Returns:

the Graph object representing the found subgraph.

setComparator

private void setComparator()